package lanQiaoBei.搜索与图论.树与图的遍历_拓扑排序;
import java.io.*;
import java.util.*;
/*利用宽度优先遍历框架完成拓扑排序
*题目如下：
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围
1≤n,m≤10^5
输入样例：

3 3
1 2
2 3
1 3
输出样例：
1 2 3
* */
public class P1 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       final static int N=100010;
       static int h[]=new int[N],e[]=new int[N],ne[]=new int[N],dig[]=new int[N],idx,n,m;
       
       static void add(int a,int b){
    	      e[idx]=b;ne[idx]=h[a];h[a]=idx++;
       }
       static void tuopu(){
    	      int q[]=new int[N],hh=0,tt=-1;
    	      for(int i=1;i<=n;i++)
    	    	  if(dig[i]==0)
    	    		  q[++tt]=i;
    	      while(hh<=tt){
    	    	    int t=q[hh++];
    	    	    for(int i=h[t];i!=-1;i=ne[i]){
    	    	    	int j=e[i];
    	    	    	if(--dig[j]==0)
    	    	    		q[++tt]=j;
    	    	    }
    	      }
    	      
    	      if(tt==n-1){
    	    	  for(int i=0;i<=tt;i++)
    	    		  System.out.print(q[i]+" ");
    	      }else System.out.print(-1);
       }
       public static void main(String[] ss) throws IOException {
		      ss=br.readLine().split(" ");
		      n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);
		      Arrays.fill(h, -1);
		      while(m-->0){
		    	   ss=br.readLine().split(" ");
		    	   int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]);
		    	   add(a,b);
		    	   dig[b]++;
		      }
		      tuopu();
	   }
}
